package gcdOfStrings;

public class Solution {
    public String gcdOfStrings(String str1, String str2) {
        // 字符串的最大公因子
        // str1 = t+t+t+t+t
        // str2 = t+t+t+t+t
        // 如果两个字符串有公因子 那么他们的公因子的长度一定是gcd(str1,str2)
        int len = gcd(str1.length(),str2.length());
        if(check(len,str1)&&check(len,str2)){
            return str1.substring(0,len);
        }
        return "";
    }
    private boolean check(int len,String target) {
        for (int i = len; i < target.length(); i++) {
            if(target.charAt(i)!=target.charAt(i-len))return false;
        }
        return true;
    }
    private int gcd(int a,int b) {
        if(b==0)return a;
        return gcd(b,a%b);
    }

}
